package codetop;


import java.util.*;

public class Code015 {

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>>ans =new ArrayList<>();
        Arrays.sort(nums);
        int pre=0;
        for (int i = 0; i < nums.length; i++) {
            if (i!=0){
                if (nums[i]==pre)continue;
            }
            pre=nums[i];
            if (pre>0)break;
            int sum=0-pre;
            int left=i+1;
            int right=nums.length-1;
            Set<Integer> set=new HashSet<>();
            while (left<right){
                if (nums[left]+nums[right]==sum){
                    if (!set.contains(nums[left])&&!set.contains(nums[right])){
                        List<Integer>list=new ArrayList<>();
                        list.add(pre);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        ans.add(list);
                        set.add(nums[left]);
                        set.add(nums[right]);
                    }
                    left++;
                    right--;
                }else if (nums[left]+nums[right]<sum){
                    left++;
                }else right--;
            }
        }
        return ans;
    }
}
